/*
 * (C) Copyright 2014-2018, by Dimitrios Michail
 *
 * JHeaps Library
 * 
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.jheaps.monotone

import org.jheaps.Heap
import org.jheaps.annotations.ConstantTime
import org.jheaps.annotations.LogarithmicTime
import java.io.Serializable
import kotlin.math.min

/**
 * Base abstract implementation of a radix heap.
 *
 * @author Dimitrios Michail
 *
 * @param <K>
 * the key type
</K> */
abstract class AbstractRadixHeap<K>() : Heap<K>, Serializable {
    /**
     * The buckets as lists. We use array-lists instead of linked-lists, to be
     * cache friendly.
     */
    protected lateinit var buckets: Array<MutableList<K>>

    /**
     * Number of elements
     */
    protected var size: Long = 0

    /**
     * Last deleted key. This value is used to distribute elements in the
     * buckets. Should be initialized with the [.minKey] value.
     */
    protected var lastDeletedKey: K? = null

    /**
     * The current minimum value (cached)
     */
    protected var currentMin: K? = null

    /**
     * The current minimum value bucket (cached)
     */
    protected var currentMinBucket: Int = 0

    /**
     * The current minimum value position in bucket (cached)
     */
    protected var currentMinPos: Int = 0

    /**
     * Minimum key allowed
     */
    protected var minKey: K? = null

    /**
     * Maximum key allowed
     */
    protected var maxKey: K? = null

    /**
     * {@inheritDoc}
     */
    @ConstantTime
    override fun findMin(): K {
        if (size == 0L) {
            throw NoSuchElementException()
        }
        return currentMin!!
    }

    /**
     * {@inheritDoc}
     *
     * @throws IllegalArgumentException
     * if the key is null
     * @throws IllegalArgumentException
     * if the key is less than the minimum allowed key
     * @throws IllegalArgumentException
     * if the key is more than the maximum allowed key
     * @throws IllegalArgumentException
     * if the key is less than the last deleted key (or the minimum
     * key allowed if no key has been deleted)
     */
    @ConstantTime(amortized = true)
    override fun insert(key: K) {
        if (key == null) {
            throw IllegalArgumentException("Null keys not permitted")
        }
        if (compare(key, maxKey) > 0) {
            throw IllegalArgumentException("Key is more than the maximum allowed key")
        }

        if (compare(key, lastDeletedKey) < 0) {
            throw IllegalArgumentException("Invalid key. Monotone heap.")
        }
        val b: Int = computeBucket(key, lastDeletedKey!!)
        buckets[b].add(key)

        // update current minimum cache
        if (currentMin == null || compare(key, currentMin) < 0) {
            currentMin = key
            currentMinBucket = b
            currentMinPos = buckets[b].size - 1
        }

        size++
    }

    /**
     * {@inheritDoc}
     *
     * The cost of this operation is amortized O(logC) assuming the heap
     * contains keys in the range [0, C] or equivalently [a, a+C].
     */
    @LogarithmicTime(amortized = true)
    override fun deleteMin(): K {
        if (size == 0L) {
            throw NoSuchElementException()
        }

        // updated last deleted key
        lastDeletedKey = currentMin

        if (currentMinBucket == 0) {
            buckets.get(currentMinBucket).removeAt(currentMinPos)

            // update minimum cache
            currentMin = null
            currentMinBucket = EMPTY
            currentMinPos = EMPTY
            if (--size > 0) {
                findAndCacheMinimum(0)
            }
        } else {
            var newMin: K? = null
            var newMinBucket: Int = EMPTY
            var newMinPos: Int = EMPTY

            // redistribute all elements based on new lastDeletedKey
            var pos: Int = 0
            for (`val`: K in buckets[currentMinBucket]) {
                if (pos != currentMinPos) {
                    val b: Int = computeBucket(`val`, lastDeletedKey!!)
                    assert(b < currentMinBucket)
                    buckets[b].add(`val`)

                    if (newMin == null || compare(`val`, newMin) < 0) {
                        newMin = `val`
                        newMinBucket = b
                        newMinPos = buckets[b].size - 1
                    }
                }
                ++pos
            }
            buckets[currentMinBucket].clear()

            // update minimum cache
            currentMin = newMin
            currentMinBucket = newMinBucket
            currentMinPos = newMinPos
            if (--size > 0) {
                findAndCacheMinimum(currentMinBucket + 1)
            }
        }

        return lastDeletedKey!!
    }

    @get:ConstantTime
    override val isEmpty: Boolean
        get() {
            return size == 0L
        }

    /**
     * {@inheritDoc}
     */
    @ConstantTime
    override fun size(): Long {
        return size
    }

    /**
     * {@inheritDoc}
     */
    override fun clear() {
        for (bucket in buckets) {
            bucket.clear()
        }
        size = 0
        lastDeletedKey = minKey
        currentMin = null
        currentMinBucket = EMPTY
        currentMinPos = EMPTY
    }

    /**
     * Always returns `null` since this heap uses the
     * [natural ordering][Comparable] of its keys.
     *
     * @return `null` since this heap uses the natural ordering of its
     * keys
     */
    override fun comparator(): Comparator<in K?>? {
        return null
    }

    /**
     * Compares its two arguments for order. Returns a negative integer, zero,
     * or a positive integer as the first argument is less than, equal to, or
     * greater than the second.
     *
     * @param o1
     * the first object to be compared.
     * @param o2
     * the second object to be compared.
     * @return a negative integer, zero, or a positive integer as the first
     * argument is less than, equal to, or greater than the second.
     */
    protected abstract fun compare(o1: K, o2: K?): Int

    /**
     * Compute the bucket of a key based on a minimum key.
     *
     * @param key
     * the key
     * @param minKey
     * the minimum key
     * @return the bucket where the key should go
     */
    protected fun computeBucket(key: K, minKey: K): Int {
        return (1 + min(msd(key, minKey).toDouble(), (buckets.size - 2).toDouble())).toInt()
    }

    /**
     * Compute the most significant digit which is different in the binary
     * representation of two values, or -1 if numbers are equal.
     *
     * @param a
     * the first value
     * @param b
     * the second value
     * @return the most significant digit which is different or -1 if numbers
     * are equal
     */
    protected abstract fun msd(a: K, b: K): Int

    /**
     * Helper method for finding and caching the minimum. Assumes that the heap
     * contains at least one element.
     *
     * @param firstBucket
     * start looking for elements from this bucket
     */
    private fun findAndCacheMinimum(firstBucket: Int) {
        if (currentMin == null) {
            // find first non-empty bucket
            currentMinBucket = EMPTY
            for (i in firstBucket until buckets.size) {
                if (buckets[i].isNotEmpty()) {
                    currentMinBucket = i
                    break
                }
            }
            // find new minimum and its position (beware of cached values)
            currentMinPos = EMPTY
            if (currentMinBucket >= 0) {
                var pos: Int = 0
                for (`val`: K in buckets[currentMinBucket]) {
                    if (currentMin == null || compare(`val`, currentMin) < 0) {
                        currentMin = `val`
                        currentMinPos = pos
                    }
                    ++pos
                }
            }
        }
    }

    companion object {

        /**
         * Denotes that a key does not belong to a bucket
         */
        protected val EMPTY: Int = -1
    }
}
